package bm3;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/19 23:44
 * BM3.链表中的节点每 k 个一组翻转
 * https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 利用递归
    public ListNode reverseKGroup (ListNode head, int k) {
        // 先找到每次翻转的链表的尾部
        ListNode tail = head;
        int count = k;
        while (count-- != 0) {
            if (tail == null) {
                // 说明最后一组不足 k 个, 则不翻转
                return head;
            }
            tail = tail.next;
        }
        // 反转每组节点
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        // 继续翻转下一组
        head.next = reverseKGroup(tail, k);
        // 返回头指针
        return head;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
